Bazy danych są obecnie jedną z najważniejszych dziedzin informatyki, pozwalając na przechowywanie i przetwarzanie masywów danych. Obecnie coraz popularniejsze stają się rozwiązania baz pamięciowych baz danych (ang. in-memory), które nie przechowują danych na dysku, lecz w pamięci operacyjnej systemu, pozwalając na szybszy dostęp do nich.
Mimo wszystko, implementacja takich baz może opierać się na różnch strukturach, które charakteryzują się różną wydajnością poszczególnych operacji takich jak odczyt, zapis czy modyfikacja.
Z tego też powodu wybraliśmy 3 różne struktury pamięciowe, a następnie zmieżyliśmy czas poszczególnych wykonywania wielokrotnego zapisu, odczytu, odczytu sekwencyjnego, modyfikacji oraz usuwania dla baz danych o różnej wielkości oraz zajętości.
Na podstawie wyników jesteśmy w stanie stwierdzić, że struktury oparte na słowniku pozwalają na najwydajniejsze wstawianie oraz odczyt danych, a te na T-Drzewie na odczyt sekwencyjny, zapewniając bardzo dobre wyniki względem pozostałych struktur.
Kod projektu dostępny jest pod adresem: https://github.com/Cheriit/memory-structures-performance
Wstęp do pracy opisujący motywacje, wybrany problem oraz cel pracy.
Motywem przewodnim pracy jest chęć sprawdzenia w działaniu różnych konceptów struktur pamięciowych, które opisane zostaną w dalszej części pracy.
Problem został określony jako pytanie: Która z wybranych struktur pamięciowych w zadanych zmiennych warunkach okaże się najwydajniejsza dla różnych operacji?
Do przeprowadzonych eksperymentów wybrane zostały następujące struktury:
Struktury dobrane zostały na względ na swoją różnorodność i chęć sprawdzenia w praktyce różnych podejść do operowania na danych.
Celem pracy jest analiza porównawcz wybranych struktur pamięciowych, w odniesieniu do serii testów, których zadaniem jest sprawdzenie szybkości danych rozwiązań, dla operacji:
Koncepty testów oparte zostały na propozycji zaprezentowanej w A Study of Index Structures for Main Memory Database Management Systems.
Jako hipotezę badawczą przypuszczamy największą wydajność struktur hashowych takich jak słownik dla operacji dodawania, odczytu pojedynczej wartości oraz usuwania, a także najlepszą wydajność T-Drzewa dla odczytu sekwencyjnego wartości w przedziale.
W sekcji tej znajduje się informacja odnośnie sposobu implementacji każdej ze struktur. Wszystkie struktury zostały zaimplementowane w języku Python.
Implementacja tej bazy opiera się na wbudowanej strukturze listy, której zadaniem jest przechowywanie wielu zmiennych w jednym obiekcie.
def add(self, key: int, value: T) -> bool:
for item in self.items:
if item[0] == key:
return False
self.items.append((key, value))Kod prezentujący metodę dodawania elementu do listy.
Metoda przyjmująca 2 argumenty: key (liczba całkowita) oraz value.
Operacja ta wykonywana jest na istniejącej bazie danych. Do bazy
danych dodawana jest para (key, value) z unikalnym kluczem
w postaci liczby całkowitej. Tuż po wywołaniu metody, baza danych
sprawdzana jest pod kątem występowania klucza w bazie.
Jeżeli klucz znajduje się w bazie danych, operacja jest przerywana, zwrócone zostanie False, w przeciwnym wypadku para dodawana jest do bazy danych
def get(self, key: int) -> T:
for item in self.items:
if item[0] == key:
return item[1]
return NoneKod prezentujący metodę odczytującą element z listy.
Metoda przyjmująca 1 argument w postaci liczby całkowitej -
key.
Odczytywanie z listy zaimplementowane jest za pomocą pętli for przeszukującej całą bazę danych. Pętla wykonywana jest do pierwszego wystąpienia poszukiwanego klucza.
Jeżeli podczas przeszukiwania listy klucz nie zostanie znaleziony,
zwracane jest None, reprezentujące wartość pustą lub
wartość, która nie istnieje.
def get_range(self, key_from: int, key_to: int) -> list[T]:
to_return = []
for item in self.items:
if key_from <= item[0] <= key_to:
to_return.append(item[1])
return to_returnKod prezentujący metodę odczytujący sekwencje elementów z listy.
Metoda przyjmuje 2 argumenty - key_from oraz
key_to, których postacią są 2 liczby całkowite.
Do operacji odczytu sekwencyjnego z listy wykorzystywana jest pętla
for. Przeszukiwana jest zawsze cała lista w celu znalezienia wartości,
dla kluczy z przedziału od key_from do
key_to.
Wyniki zbierane są w tymczasową listę to_return, która
jest zawsze zwracana - niezależnie czy jest pusta czy nie.
def update(self, key: int, new_value: T) -> bool:
for item in self.items:
if item[0] == key:
index_to_update = self.items.index(item)
self.items[index_to_update] = (key, new_value)
return True
return FalseKod prezentujący metodę aktualizacji elementu w liście.
Do poprawnego wywołania metody aktualizacji wymagane jest podanie 2
argumentów: klucza - key oraz nowej wartości -
new_value.
Operacja aktualizowania wartości przy danym kluczu odbywa się za
pomocą pętli for. Pętla wykonywana jest do pierwszego wystąpienia danego
klucza, dla którego wartość value zostaje zmieniona przez
wskazane new_value.
Jeżeli klucz nie znajduje się w bazie danych zwrócona zostanie
wartość False.
def delete(self, key: int) -> bool:
for item in self.items:
if item[0] == key:
self.items.remove(item)
return True
return FalseKod prezentujący metodę usuwającą element z listy.
Metoda przyjmująca tylko 1 argument, czyli liczbę całkowitą
key.
Operacja usuwania odbywa się za pomocą pętli for. Przeszukiwanie w
celu znalezienia klucza wykonywane jest aż do znalezienia owego klucza.
Tuż przed przerwaniem wykonywania pętli, para z danym kluczem zostaje
usunięta, zwrócone zostanie True.
W przeciwnym wypadku, jeżeli para z danym kluczem nie istnieje metoda
zwraca wartość False.
Implementacja tej bazy opiera się na wbudowanej strukturze słownika (ang. dictionary), której zadaniem jest przechowywanie wielu par o postaci klucz-wartość w jednej zmiennej.
def add(self, key: int, value: T) -> bool:
if key in self.items.keys():
return False
self.items[key] = valueKod prezentujący metodę dodającą element do słownika.
Metoda przyjmująca 2 argumenty: klucz (key) oraz wartość
(value). Klucz jest unikalną wartością w postaci liczby
całkowitej.
Dodawanie elementu do słownika rozpoczyna się od sprawdzenia czy
klucz znajduje się w bazie danych. Jeśli tak, zwracana jest wartość
False, w przeciwnym przypadku do klucza key
przypisywana jest wartość value.
def get(self, key: int) -> T:
return self.items.get(key)Kod prezentujący metodę odczytującą element ze słownika.
Metoda przyjmuje 1 argument, czyli liczbę całkowitą jako
key.
Pobierana i zwracana jest wartość dla danego klucza, jeżeli klucz nie
znajduje się w słowniku, zwracane zostaje None.
def get_range(self, key_from: int, key_to: int) -> list[T]:
to_return = []
for key in self.items.keys():
if key_from <= key <= key_to:
to_return.append(self.items[key])
return to_returnKod prezentujący metodę odczytującą sekwencje elementów ze słownika.
Metoda przyjmuje 2 argumenty w postaci liczb całkowitych:
key_from, key_to, które tworzą przedział
działania pętli for.
Przeszukiwany jest cały słownik w poszukiwaniu pasujących kluczy.
Wszystkie znalezione wartości umieszczane są w liście
to_return, która zawsze jest zwracana, nawet jeżeli jest
pusta.
def update(self, key: int, new_value: T) -> bool:
if key not in self.items.keys():
return False
self.items[key] = new_valueKod prezentujący metodę aktualizującą elementy w słowniku.
Do poprawnego działania metody wymagane są 2 argumenty: klucz
(key) w postaci liczby całkowitej oraz nową wartość
(new_value).
Po wywołaniu metody, słownik sprawdzany jest pod kątem występowania
danego klucza - aby przypadkiem nie utworzyć pary z kluczem, który
wcześniej nie istniał. Po poprawnym zweryfikowaniu słownika, wartość dla
klucza zostaje zastąpiona przez wartość new_value.
W przypadku, gdy klucz nie istnieje w słowniku, zwracana zostaje
wartość False.
def delete(self, key: int) -> bool:
if key not in self.items.keys():
return False
self.items.pop(key)Kod prezentujący metodę usuwającą element ze słownika.
Metoda do poprawnego działania wymaga podania 1 argumentu, czyli
klucza (key) w postaci liczby całkowitej.
Na początku operacji słownik sprawdzany jest pod kątem występowania
klucza, jeśli klucz znajduje się w bazie danych, jest usuwany. W
przeciwnym wypadku zostaje zwrócona wartość False.
T-Drzewo zostało zaimplementowane w języku Python.
W tym celu została stworzona klasa Node, która odpowiada jednostce pojedynczego węzła w drzewie. Całość została stworzona na podstawie A Study of Index Structures for Main Memory Database Management Systems.
Jest to struktura drzewiasta wywarzona, której każdy wierzchołek
zawiera wskaźnik do wierzchołka zawierającego wartości indeksu mniejsze
od key_from po lewej oraz większe od key_to po
prawej. Wewnętrznie przechowuje ona wartości dla indeksów pomiędzy
key_from oraz key_to.
class Node:
__slots__ = ('left', 'right', 'key_from', 'key_to', 'values')
def __init__(self, key, value, node_size=100, left=None, right=None):
self.left = left
self.right = right
self.key_from = key // node_size * node_size
self.key_to = key // node_size * node_size + node_size - 1
self.values = {key: value}Kod prezentujący klasę węzła w T-Drzewie.
def add(self, key: int, value: T) -> bool:
if search(self.root, key) is not None:
return False
self.root = insert(self.root, key, value)
self.size += 1
self.check()
def insert(node, key, value):
if node is None:
return Node(key, value)
if key < node.key_from:
node.left = insert(node.left, key, value)
elif key > node.key_to:
node.right = insert(node.right, key, value)
else:
node.values[key] = value
return nodeKod prezentujący metodę dodającą element do drzewa wraz z metodą pomocniczą.
def check(self):
if depth(self.root.left) - depth(self.root.right) > 1:
self.root = rotation_right(self.root)
elif depth(self.root.right) - depth(self.root.left) > 1:
self.root = rotation_left(self.root)
def depth(node):
if node is None:
return 0
else:
left_depth = depth(node.left)
right_depth = depth(node.right)
if left_depth > right_depth:
return left_depth + 1
else:
return right_depth + 1
def rotation_right(node):
y = node.left
t = y.right
y.right = node
node.left = t
return y
def rotation_left(node):
y = node.right
t = y.left
y.left = node
node.right = t
return yKod reprezentujący implementacje metod pomocniczych służących do rotacji drzewa.
Metoda do poprawnego działania wymaga 2 argumentów: klucza
(key) oraz wartości (value).
Dane dodawane są nawet do nieistniejącego drzewa, jeśli drzewo nie istnieje to przy pierwszej dodawanej wartości jest tworzone.
Na początku operacji drzewo jest przeszukiwane, by uniknąć próby
dodania istniejącego klucza do drzewa - w przypadku, gdy klucz istnieje
w bazie danych, zwrócona zostanie wartość False.
Następnie wartość jest już dodawana do drzewa według założeń drzewa w
postaci wpisu do węzła. Każdy węzeł ma równy rozmiar i przechowuje równą
liczbę wpisów w postaci par klucz-wartość. Dodatkowo atrybutami
opisującymi węzeł są granice przedziału kluczy: key_from,
key_to. Zaraz po dodaniu pary do drzewa, zwiększany jest
licznik rozmiaru bazy danych oraz następuje sprawdzenie drzewa za pomocą
metody check(), która ma na celu sprawdzenie możliwości
rotacji drzewa w lewo, bądź w prawo.
def get(self, key: int) -> T:
res = search(self.root, key)
if res is not None:
return res.values[key]
return None
def search(root, key):
if root is None:
return root
if root.key_from <= key <= root.key_to:
if key in root.values:
return root
if root.key_from > key:
return search(root.left, key)
return search(root.right, key)Kod reprezentujący implementację odczytywania wartości z drzewa wraz z metodą pomocniczą.
Wymaganiem metody jest 1 argument: klucz (key).
Wykorzystywany jest on do przeszukania drzewa w celu znalezienia
wartości o podanym kluczu. Na początku szukany jest węzeł który zawiera
dany klucz, przeszukiwanie odbywa się za pomocą wzdłużnego przechodzenia
drzewa (pre-order). Gdy węzeł zostanie znaleziony, pobierana
jest z niego wartość jeśli istnieje. Wartość ta zostaje zwrócona. W
przeciwnym wypadku, jeśli nie zostanie znaleziony węzeł spełniający
wymagania, zwracane jest None.
def get_range(self, key_from: int, key_to: int) -> list[T]:
result = []
for key in range(key_from, key_to + 1):
temp = search(self.root, key)
if temp is not None:
result += [[key, temp.values[key]]]
return resultKod reprezentujący implementację odczytywania sekwencji wartości z drzewa.
Metoda przyjmuje 2 argumenty: key_from oraz
key_to, które jako liczby całkowite są skrajnymi
wartościami przedziału kluczy.
Odczyt sekwencyjny odbywa się za pomocą zwykłego Odczytu, ale z
dodatkiem pętli for, która odpowiada za pracę na przedziale liczbowym.
Wszystkie znalezione pary umieszczane są w tymczasowej liście
result, która niezależnie od rozmiaru, jest zwracana.
def update(self, key: int, new_value: T) -> bool:
res = update(self.root, key, new_value)
if res is None:
return False
def update(root, key, new_value):
if root is None:
return root
if root.key_from <= key <= root.key_to:
if key in root.values:
root.values[key] = new_value
return root
if root.key_to < key:
return update(root.right, key, new_value)
return update(root.left, key, new_value)Kod reprezentujący implementację aktualizacje wartości drzewa wraz z metodą pomocniczą.
Do poprawnego działania wymagane jest podanie 2 argumentów: klucz
(key) oraz nowa wartość (new_value).
Podobnie jak w przypadku operacji Odczytu, znalezienie węzła do
zmiany odbywa się przez przechodzenie drzewa wzdłuż
(pre-order). Po znalezieniu odpowiedniego węzła, sprawdzana
jest obecność konkretnego klucza w węźle. Jeśli klucz znajduje się w
węźle, następuje zmiana wartości na new_value.
W przeciwnym wypadku operacja jest przerywana i zwracana jest wartość
None.
def delete(self, key: int) -> bool:
res = deleteNode(self.root, key)
if not res[1]:
return False
self.size -= 1
def deleteNode(root, key, deleted=False):
if root is None:
return root, deleted
if isinstance(root, tuple):
r = root[0]
else:
r = root
if (r.key_from <= key <= r.key_to) and (len(r.values) > 0):
if key in r.values:
del r.values[key]
deleted = True
if len(r.values) == 0:
tmp = deleteNode(r, r.key_from)
if tmp is not None:
r = tmp[0]
else:
if key < r.key_from:
tmp = deleteNode(r.left, key)
if tmp is not None:
r.left = tmp[0]
elif key > r.key_to:
tmp = deleteNode(r.right, key)
if tmp is not None:
r.right = tmp[0]
else:
if r.left is None:
temp = r.right
r = None
return temp, deleted
elif r.right is None:
temp = r.left
r = None
return temp, deleted
temp = minValueNode(r.right)
r.key = temp[0]
r.right = deleteNode(r.right, temp[0])[0]
return r, deletedKod reprezentujący implementację usuwania wartości z drzewa wraz z metodą pomocniczą.
Metoda do poprawnego działania wymaga 1 argumentu, czyli klucza
(key).
Po rozpoczęciu operacji usuwania klucza z drzewa następuje wyszukiwanie odpowiedniego węzła przechowującego dany klucz.
Następnie, jeżeli klucz zostanie znaleziony sprawdzane są pary w węźle, by zweryfikować obecność klucza do usunięcia.
Po poprawnej weryfikacji klucz zostaje usunięty z węzła, po czym sprawdzany jest rozmiar węzła. Jeżeli rozmiar węzła jest równy 0, następuje usunięcie węzła z drzewa, w przeciwnym wypadku zwracana jest para składająca się z głównego węzła i flagi informującej o usunięciu klucza.
Za pomocą flagi sprawdzany jest status wykonania operacji, jeśli
usuwanie powiodło się to rozmiar bazy danych jest zmniejszony o 1, jeśli
nie zwracana jest wartość False.
W tym rozdziale zostanie opisana obrana metodologia badań uwzględniająca poszczególne operacje, środowisko oraz sposób przeprowadzenia badań.
Do badań wybrano 6 różnych operacji:
Dodawanie - do istniejącej bazy danych dodano n różnych
nowych wartości o kolejnych wartościach indeksu, rozpoczynających się od
wartości większej o 1 od największej obecnie istniejących.
Pod każdy z kluczy generowano losowo dane osoby (imię, nazwisko, numer
PESEL, adres mailowy, numer telefonu, wiek oraz adres).
Odczyt - do odczytu wybierano każdorazowo losową wartość ze wszystkich wartości indeksu bazy danych.
Odczyt sekwencyjny - do odczytu wybierano każdorazowo losową
wartość początkową przedziału. Na jej podstawie każdorazowo dokonano
100 odczytów sekwencyjnych wartości kluczy.
Aktualizacja - do aktualizacji wybierano każdorazowo losową wartość ze wszystkich wartości indeksu bazy danych, a następnie dokonywano ponownego generowania danych osoby.
Usuwanie - do usuwania wybrano każdorazowo losową wartość, od wartości minimalnej, do maksymalnej z bazy danych. Niektóre odczyty mogły próbować usunąć wartość nieistniejącą.
Połączenie operacji - operacja składająca się z łańcucha 600
operacji odczytu z całej bazy danych, 600 operacji dodania
wartości o nowych indeksach wzorem operacji dodania oraz 600 operacji
usunięcia dodanych przed chwilą danych.
W celu uzyskania miarodajnych wyników, objęto poniższą metodologie badań.
Każda z operacji została wykonana 3000 razy pod rząd, w
celu uniknięcia tzw. outlayerów, mierząc czas wykonania zbioru operacji.
Pozwoliło to osiągnąć uśrednione czasy dla każdej z operacji. W czas
operacji jest również wliczony losowy wybór wartości z przedziału
zależnego od wielkości danych.
Sekwencje operacji zostały uruchomione na bazach danych z różną,
początkową ilością danych. zaczynając na 10,000 rekordach,
kończąc na 100,000 z krokiem 10,000.
W celu zminimalizowania wpływu usług uruchamianych przez system w tle
niezależnie od użytkownika, generując outlayery, cały proces został
wykonany 3 razy, pozwalając na uśrednienie wyników
badań.
Środowisko do przeprowadzenia badań stanowi komputer wyposażony w:
21H23.11.1W ramach przeprowadzanych badań, nie dokonywano żadnych operacji na wyżej wymienionym systemie.
W tej sekcji zawiera się wizualizacja oraz opis wyników przeprowadzonych badań.
Zauważyć można, że w procesie dodawania najwolniejsza jest baza danych oparta na liście, gdzie jej złożoność rośnie mniej-więcej liniowo.
Następna w kolejności jak chodzi o prędkość jest baza oparta na T-Drzewie dla węzła o wielkości 100, którego złożoność rożnie mniej więcej liniowo W przypadku dwóch pozostałych baz opartych na T-Drzewach zauważyć można, że rosną one bardzo powoli.
Najszybszą operację dodawania posiada baza oparta na słowniku, której to czas odczytu jest stały.
Operacje odczytu losowego prezentują się podobie do operacji dodawania danych.
Najwolniejszy odczyt posiada struktura listowa, następnie struktury oparte na T-Drzewie, a najszybsza jest struktura oparta na słowniku, która to jest jedyna niezależna od wielkości bazy danych.
Operacja odczytu sekwencyjnego na bazie opartej na słowniku jest najwolniejsza. Nieznacznie szybsza jest ta oparta na liście oraz na T-Drzewie z węzłem o wielkości 100.
Znacznie szybsze są struktury oparte na T-Drzewie z węzłami o wielkościach 500 oraz 1000.
Wszystkie struktury wykazały tutaj złożoność liniową.
Zdecydowanie najwolniejszą strukturą do tej operacji jest lista, której to złożoność rośnie liniowo.
Wszystkie pozostałe struktury wykonują tą operację znacznie szybciej. Jednak warto zauważyć, że poza listą, T-Drzewo z węzłem o wielkości 100 widocznie zależy od wielkości bazy danych.
Usuwanie danych z listy zajmuje najwięcej czasu i rośnie ono liniowo.
Następna jest baza oparta na T-Drzewie o wielkości 100, 1000 oraz 500, które rosną logarytmicznie.
Najszybsze jest operowanie na strukturze słownika, które rośnie nieznacznie w zależności od wielkości bazy danych.
Połączenie operacji prezentuje się analogicznie do wykresu operacji dodawania, gdzie operowanie na liście zajmuje najdłużej, następnie jest operowanie na T-Drzewie o węźle z wielkością 100, 1000, 500 oraz na słowniku.
Wyniki zaprezentowane w poprzedniej sekcji umożliwiają wyciągnięcie następujących wniosków.
W większości testów (w szczególności scenariuszach jak dodawanie, czy aktualizacja) widać główne wady listy, z uwagę na potrzebę przeszukiwania struktury. Sam początkowy czas niezbędny do wykonywania operacji jest stosunkowo wysoki względem pozostałych struktur.
Struktura słownika prezentuje się najlepiej pod względem wydajności dla wszystkich operacji poza odczytem sekwencyjnym. Wynika to z tego, że jest ona oparta na stałym czasie dostępu poprzed obliczanie lokalizacji na podstawie podanego klucza, jako struktura hashowa.
T-Drzewo w istotnym stopniu zależy od wielkości bazy danych, z uwagi na to, że jest to struktura drzewiasta. Operacje takie dodawanie czy usuwanie posiadają narzut czasu który wynika z potrzeby balansowania struktury, a jedynym narzutem czasu dla odczytu i aktualizacji jest samo schodzenie niżej w strukturze bazy danych. Czyni to operacje odczytu niezwykle efektywną.
Dla odczytu sekwencyjnego widać zbliżone wyniki dla listy, słownika i t-drzewa w wariancie 100-węzłowym. Fakt znalezienia się w tym gronie słownika tłumaczy to, że w tym przypadku generalna zaleta polegająca na przeszukiwaniu struktury zostaje zniwelowana z uwagi na charakter operacji, w której ułożone kolejno po sobie dane faworyzują struktury takie jak lista, czy T-Drzewo, których to kolejne dane są łatwo dostępne oraz ułożone obok siebie w pamięci.
Z używanych wariantów T-Drzew widać znaczące różnice, zwłaszcza między wariantem 100-węzłowym, resztą. Wynika to głównie z wielkości węzłów na poziom, powodujące częste potrzeby tworzenia nowych poziomów, a w wyniku ciągłego kopiowania danych i samych operacji na strukturze, wysoki czas operacji.
Ciekawą zależność można natomiast zaobserwować między wersją 500 i 1000 węzłową. Przypuszczalnie powodem takiego stanu rzeczy jest problem z odpowiednim wyważeniem przypadających węzłów, co może być tematem przyszłych badań.
W przypadku bazy danych o wielkości 100,000 elementów, przy węźle o rozmiarze 1000, w dużej mierze przegląd elementów zaczyna momentami przypominać przegląd listy o stałej długości 1000. Czym większy jest węzeł, tym dłużej zajmuje jego przegląd, natomiast podowuje on zmniejszenie samej struktury T-Drzewa poprzez zmniejszenie liczby węzłów. Dodatkowo zmniejsza się częstość równoważenia drzewa, gdyż potrzebujemy dodać więcej elementów, żeby być zmuszeni na dodanie kolejnego węzła.
Dane uzyskane w ramach eksperymentu popierają hipotezę badawczą, gdzie faktycznie najszybszy odczyt, zapis pojedynczych wartości oraz usuwanie jest najszybsze w strukturach hash’owych takich jak słownik, a odczyt w przedziale najszybszy jest w T-Drzewie.